package com.coder.algorithm.offer_2;

/**
 * 打印从 1 到最大的 n 位数
 *
 * @author yuhushuan
 * @date 2020/6/13 16:04
 */
public class _17_1_Print1ToMaxOfNDigit {
    public static void main(String[] args) {

        int[] number;

        // 测试打印函数
        number = new int[]{0};
        printNumber(number);
        number = new int[]{0, 0, 0};
        printNumber(number);
        number = new int[]{0, 9};
        printNumber(number);
        number = new int[]{9, 9, 9, 9, 9, 9, 9, 9, 9, 9};
        printNumber(number);

        // 功能测试
        System.out.println("==============");
        print_solution2(0);
        print_solution2(3);

        // 测试增加函数
        System.out.println("==============");
        number = new int[]{0};
        increment(number);
        printNumber(number);

        number = new int[]{7, 9};
        increment(number);
        printNumber(number);

        number = new int[]{7, 9, 9};
        increment(number);
        printNumber(number);

        number = new int[]{9, 9, 9, 9, 9, 9, 9, 9, 9, 9};
        increment(number);
        printNumber(number);

    }

    private static void print_solution1(int n) {
        if (n <= 0) {
            return;
        }
        int[] number = new int[n];
        while (increment(number)) {
            printNumber(number);
        }
    }

    private static boolean increment(int[] number) {
        if (number == null) {
            return false;
        }
        boolean isOverflow = false;
        int nTakeOver = 0;
        for (int i = number.length - 1; i >= 0; --i) {
            number[i] = number[i] + nTakeOver;
            // 个位加 1
            if (i == number.length - 1) {
                number[i]++;
            }
            if (number[i] == 10) {
                if (i == 0) {
                    isOverflow = true;
                } else {// 向前进 1
                    number[i] -= 10;
                    nTakeOver = 1;
                }
            } else {
                break;
            }
        }
        return !isOverflow;
    }

    private static void printNumber(int[] number) {
        if (number == null) {
            return;
        }
        boolean allZero = true;
        for (int i = 0; i < number.length; ++i) {
            if (number[i] != 0) {
                allZero = false;
            }
            if (!allZero) {
                System.out.print(number[i]);
            }
        }
        if (allZero) {
            System.out.print(0);
        }
        System.out.println();
    }

    private static void print_solution2(int n) {
        if (n <= 0) {
            return;
        }
        int[] number = new int[n];
        for (int i = 0; i < 10; ++i) {
            number[0] = i;
            print(number, 0);
        }
    }

    private static void print(int[] number, int index) {
        if (index == number.length - 1) {
            printNumber(number);
            return;
        }
        index += 1;
        for (int i = 0; i < 10; ++i) {
            number[index] = i;
            print(number, index);
        }
    }


}
